package interview_59_1

func maxSlidingWindow(nums []int, k int) []int {

	//[10 9 8] 7 6 5 4 3 2 1
	//10 [9 8 7] 6 5 4 3 2 1
	//10 9 [8 7 6] 5 4 3 2 1
	//10 9 8 [7 6 5] 4 3 2 1
	//10 9 8 7 [6 5 4] 3 2 1
	//10 9 8 7 6 [5 4 3] 2 1
	//10 9 8 7 6 5 [4 3 2] 1
	//10 9 8 7 6 5 4 [3 2 1]

	window := make([]int, 0, k)
	maxIndex := 0
	maxSlice := make([]int, 0, k)
	//res := make([]int, 0, k)
	//var window []int
	for i, num := range nums {

		window = append(window, num)

		if i < k && num > nums[maxIndex] {
			maxIndex = i
		}

		if len(window) == k {
			//计算窗口最大值
			maxSlice = append(maxSlice, nums[maxIndex])
		}

		if len(window) > k {

			loseIndex := i - k
			window = window[1:]

			//计算窗口最大值
			if maxIndex == loseIndex {
				// 重新计算窗口最大值
				max := 0
				for k, v := range window {
					if window[max] < v {
						max = k
					}
				}
				maxIndex = i - k + 1 + max
			} else {
				// 比较两个数大小
				if nums[maxIndex] <= num {
					maxIndex = i
				}
			}
			maxSlice = append(maxSlice, nums[maxIndex])
		}

	}

	return maxSlice
}

// curr - k + 1 - res = nums所在索引
func getMaxIndex(window []int) int {

	max := 0
	for k, v := range window {
		if window[max] < v {
			max = k
		}
	}

	return max
}
